class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ret;
        int m = matrix.size(), n = matrix[0].size();
        int top = 0, left = 0, right = n - 1, botton = m - 1;

        while (left <= right && top <= botton)
        {
            if (left == right && top == botton && ret.size() < m * n)
                ret.push_back(matrix[top][left]);

            for (int i = left; i < right&& ret.size() < m * n; ++i)
                ret.push_back(matrix[top][i]);

            for (int i = top; i < botton&& ret.size() < m * n; ++i)
                ret.push_back(matrix[i][right]);

            for (int i = right; i > left&& ret.size() < m * n; --i)
                ret.push_back(matrix[botton][i]);

            for (int i = botton; i > top&& ret.size() < m * n; --i)
                ret.push_back(matrix[i][left]);

            ++top;
            ++left;
            --right;
            --botton;
        }

        return ret;
    }
};

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        //检查行
        for (int i = 0; i < 9; ++i)
        {
            bool used[9]{false};
            for (int j = 0; j < 9; ++j)
            {
                if (isdigit(board[i][j]))
                {
                    if (used[board[i][j] - '1' ])
                        return false;
                    
                    used[board[i][j] - '1'] = true;
                }
            }
        }

        //检查列
        for (int i = 0; i < 9; ++i)
        {
            bool used[9]{false};
            for (int j = 0; j < 9; ++j)
            {
                if (isdigit(board[j][i]))
                {
                    if (used[board[j][i] - '1'])
                        return false;
                    
                    used[board[j][i] - '1'] = true;
                }
            }
        }

        //检查3 * 3
        int row[3]{0, 3, 6};
        int col[3]{0, 3, 6};
        for (int i = 0; i < 9; ++i)
        {
            bool used[9]{false};
            for (int j = row[i / 3]; j < row[i / 3] + 3; ++j)
            {
                for (int k = col[i % 3]; k < col[i % 3] + 3; ++k) 
                {
                    if (isdigit(board[j][k]))
                    {
                        if (used[board[j][k] - '1'])
                            return false;
                    
                        used[board[j][k] - '1'] = true;
                    }
                }
            }
        }


        return true;
    }
};

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int row = n / 2;
        int col = (n + 1) / 2;

        for (int i = 0; i < row; ++i)
        {
            for (int j = 0; j < col; ++j)
            {
                int tmp = matrix[i][j];

                //[i, j] -> [j, n - i - 1]
                //[j, n - i - 1] -> [n - i - 1, n - j - 1]
                //[n - i - 1, n - j - 1] -> [n - j - 1, i];
                //[n - j - 1, i] -> [i, j]

                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = tmp;
            }
        }
    }
};

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        bool row_flag = false, col_flag = false;

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (matrix[i][j] == 0)
                {
                    if (i == 0)
                        row_flag = true;
                    if (j == 0)
                        col_flag = true;

                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }

        for (int i = 1; i < n; ++i)
        {
            if (matrix[0][i] == 0)
                for (int j = 0; j < m; ++j)
                    matrix[j][i] = 0;
        }

        for (int i = 1; i < m; ++i)
        {
            if (matrix[i][0] == 0)
                for (int j = 0; j < n; ++j)
                    matrix[i][j] = 0;
        }

        if (row_flag)
        {
            for (int i = 0; i < n; ++i)
                matrix[0][i] = 0;
        }
            
        if (col_flag)
        {
            for (int i = 0; i < m; ++i)
                matrix[i][0] = 0;
        }
    }
};

//因为数组元素类型是int
//因此可以用第二个比特位来记录下一个状态
//到时候直接将所有元素右移一位即可
class Solution {
private:
    int dieOrLive(vector<vector<int>>& board, int m, int n)
    {
        int count_one = 0;
        for (int i = max(0, m - 1); i <= min(m + 1, (int)board.size() - 1); ++i)
        {
            for (int j = max(0, n - 1); j <= min(n + 1, (int)board[0].size() - 1); ++j)
            { 
                //printf("[%d, %d]: %d\n", i, j, ((board[i][j] & 1) == 1));

                if (!(i == m && j == n) && ((board[i][j] & 1) == 1))
                    ++count_one;
            }
        }
        //cout << "m: "<< m << " n: " << n << " " << count_one << "\n\n";

       
        if (board[m][n] & 1)
        {
            if (count_one < 2)
                return 0;
            else if (count_one <= 3)
                return 1;
            else
                return 0;
        }
        else
        {
            if (count_one == 3)
                return 1;
            return 0;
        }

    }
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size(), n = board[0].size();
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (dieOrLive(board, i, j))
                    board[i][j] |= (1 << 1);
            }
        }    

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
                board[i][j] >>= 1;
        }
    }
};